class Solution {
public:
    void nextPermutation(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (num.size() <= 1) {
            return;
        }
        int n = num.size();
        int pos = n - 1;

        while (pos > 0 && num[pos] <= num[pos - 1]) {
            --pos;
        }
        if (pos == 0) {
            reverse(num.begin(), num.end());
            return;
        }
        int pos2 = n - 1;
        while (num[pos2] <= num[pos - 1]) {
            --pos2;
        }
        swap(num[pos2], num[pos - 1]);
        reverse(num.begin() + pos, num.end());
    }
};
